#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    bool dp[10] = { 0 };

    void _Permutation(unordered_map<string, int>& hash, string& str, int count, string s)
    {
        if (count >= str.size())
        {
            hash[s];
            return;
        }
        for (int i = 0; i < str.size(); i++)
        {
            if (dp[i] == true) continue;
            s.push_back(str[i]);
            dp[i] = true;
            _Permutation(hash, str, count + 1, s);
            s.pop_back();
            dp[i] = false;
        }
    }

    vector<string> Permutation(string str) {
        unordered_map<string, int> hash;
        int count = 0;
        string s;
        _Permutation(hash, str, count, s);
        vector<string> ret;
        for (auto [x, y] : hash) ret.push_back(x);
        return ret;
    }
};